//
//  69. x的平方根.swift
//  Top600
//
//  Created by rjb on 2021/8/10.
//

import Foundation
class Solution69 {
    func mySqrt(_ x: Int) -> Int {
        var left = 0
        var right = x
        var ans = -1
        // 逼近法
        while right - left >= 0  {
            // 这句换很关键
            let mid = left + (right - left) / 2
            let tmp = mid * mid
            if tmp <= x {
                ans = mid
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return ans
    }
    // 二分法实际上时不断逼近的方法
    func mySqrt2(_ x: Int) -> Double {
        let xx: Double = Double(x)
        var left: Double = 0
        var right: Double = Double(x)
        var mid: Double = 0.0
        // 带精确位数
        // 条件是精确位不够时，就不断的进行逼近
        while right - left > 0.001 {
            mid = left + (right - left) / 2
            let tmp: Double = mid * mid
            if tmp - xx > 0.001 {
               right = mid
            } else if tmp - xx < 0.001 {
               left = mid
            } else {
                return mid
            }
        }
        return mid
    }
    static func test() {
        let solution = Solution69()
        let result = solution.mySqrt2(7)
        print(result)
    }
}
